package suanfa;

public class Eightqueens {
    private static final int n=8;
    private static final int[][] b=new int[n][n];

    public static void main(String[] args) {
        if(solvequeens()){
            printsolution();
        }else{
            System.out.println("No solution exists");
        }
    }



    private static boolean solvequeens(){
        for(int col=0;col<n;col++){
            System.out.println("col:"+col);
            if(placequeen(0,col)){
                return true;
            }
        }
        return false;
    }

    private static boolean placequeen(int row,int col){
        if(row>=n){
            System.out.println("所有皇后放置完毕");
            return true;
        }
        for(int o=0;o<n;o++){
            System.out.println("row: "+row+",o:"+o);
            if(isSafe(row,o)){
                b[row][o]=1;
                if(placequeen(row+1,0)){
                    return true;
                }
                b[row][o]=0;
            }
        }
        return false;
    }

    private static boolean isSafe(int row,int col){
        for(int i=0;i<row;i++){
            if(b[i][col]==1){
                return false;
            }
        }
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(b[i][j]==1){
                return false;
            }
        }
        return true;
    }

    private static void printsolution(){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) {
                System.out.println(b[i][j]==1?"Q ":". ");
            }
            System.out.println();
        }
    }
}
